package test.algorithm.tree;

import test.entity.TreeNode;
import test.utils.TreeNodeUtil;

import java.util.LinkedList;

import static test.utils.TreeNodeUtil.arrayToTree;

/**
 * @Projectname: algorithm-training-camp
 * @Filename: TraverseTree
 * @Author: FANSEA
 * @Date:2024/9/13 16:51
 */
// 遍历树
public class TraverseTree {
    public static TreeNode root = TreeNodeUtil.createSimpleBinaryTree();

    public static void main(String[] args) {

        Integer[] arr = {1, 2, 3, null, 5, null, 7};
        levelOrder(arrayToTree(arr));
    }
    // 前序遍历 1、2、4、5、3
    public static void preOrder(TreeNode root) {
        if (root == null){
            return;
        }
        System.out.println(root.val);
        preOrder(root.left);
        preOrder(root.right);
    }

    // 中序遍历 （最左节点）4、2、5、1、3
    public static void inOrder(TreeNode root) {
        if (root == null){
            return;
        }
        inOrder(root.left);
        System.out.println(root.val);
        inOrder(root.right);
    }

    // 后序遍历 4、5、2、3、1（头结点）
    public static void postOrder(TreeNode root) {
        if (root == null){
            return;
        }
        postOrder(root.left);
        postOrder(root.right);
        System.out.println(root.val);
    }

    // 层序遍历
    public static void levelOrder(TreeNode root) {
        if (root == null)
            return;
        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            TreeNode q = queue.poll();
            System.out.println(q.val);
            if(q.left!=null){
                queue.offer(q.left);
            }
            if(q.right!=null){
                queue.offer(q.right);
            }
        }
    }

}
